package main

import "go-study/algorithm/standard"

// 如何判断两棵二叉树是否相等

func main() {
	root1 := createTree()
	root2 := createTree()
	println(isEqual(root1, root2))
}

func isEqual(root1 *standard.BNode, root2 *standard.BNode) bool {
	if root1 == nil && root2 == nil {
		return true
	}
	if root1 == nil && root2 != nil || root1 != nil && root2 == nil {
		return false
	}
	if root1.Data == root2.Data {
		return isEqual(root1.LeftChild, root2.LeftChild) &&
			isEqual(root1.RightChild, root2.RightChild)
	}
	return false
}

func createTree() *standard.BNode {
	root := &standard.BNode{}
	node1 := &standard.BNode{}
	node2 := &standard.BNode{}
	node3 := &standard.BNode{}
	node4 := &standard.BNode{}

	root.Data = 6
	node1.Data = 3
	node2.Data = -7
	node3.Data = -1
	node4.Data = 9

	root.LeftChild = node1
	root.RightChild = node2
	node1.LeftChild = node3
	node1.RightChild = node4

	return root
}
